home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 7 / BBS in a Box - Macintosh - Volume VII (BBS in a Box) (January 1993).iso / Files / Prog / Q-R / R⁄O strsml.cpt / Ratcliff_Obershelp / strsml2.c < prev   
C/C++ Source or Header  |  1989-02-07  |  2KB  |  114 lines
  1. #include <strings.h>
  2.  
  3. int stcknum;
  4. char *ststr1l[26], *ststr2l[26], *ststr1r[26], *ststr2r[26];
  5.  
  6. /*
  7.     simil(str1, str2) - returns a value signifying how similar two 
  8.         strings are (0 - completely different, 100 - exactly the same)
  9.         using the Ratcliff/Obershelp pattern matching algorithm.
  10.         
  11.     (Code courtesy of Joe Preston published in DDJ, Nov 1988, #145, pg.12, 118).
  12. */
  13. int simil(str1, str2)
  14.     char *str1, *str2;
  15.     {
  16.     int len1, len2, ncmp, score;
  17.     char *di, *si, *de, *se, *cl1, *cl2, *cr1, *cr2;
  18.     
  19.     score = stcknum = 0;
  20.     
  21.     len1 = strlen(str1);
  22.     len2 = strlen(str2);
  23.     
  24.     if (len1 == 0 || len2 == 0)
  25.         return (score);
  26.         
  27.     pushst(str1, str1 + len1 - 1, str2, str2 + len2 - 1);
  28.     
  29.     while (stcknum != 0)
  30.         {
  31.         popst(&si, &se, &di, &de);
  32.         cl1 = si;
  33.         cl2 = di;
  34.         cr1 = se;
  35.         cr2 = de;
  36.         
  37.         if ((ncmp = compare(&si, &se, &di, &de)) != 0)
  38.             {
  39.             score += ncmp * 2;
  40.             
  41.             if (cl1 != si && cl2 != di && cl1 != si-1 || cl2 != di-1)
  42.                 pushst(cl1, si-1, cl2, di-1);
  43.             
  44.             if (se != cr1 && de != cr2 && se+1 != cr1 || de+1 != cr2);
  45.                 pushst(se+1, cr1, de+1, cr2);
  46.             }
  47.         }
  48.     return (100 * score / (len1 + len2));
  49.     }
  50.  
  51. /*
  52.     compare(si, se, di, de) - returns the largest number of characters common to both strings.
  53. */
  54. int compare(si, se, di, de)
  55.     char **si, **se, **di, **de;
  56.     {
  57.     int maxchars, l, len1;
  58.     char *i, *j, *m, *n, *s2end, *cl1, *cl2, *cr1, *cr2;
  59.     
  60.     maxchars = 0;
  61.     for (i = (*si); i <= *se - maxchars; i++)
  62.         {
  63.         len1 = *se - i;
  64.         for (j = (*di); j <= *de - maxchars; j++)
  65.             {
  66.             s2end = j + len1;
  67.             if (s2end > *de)
  68.                 s2end = *de;
  69.             for (m = i, n = j, l = 0; *m == *n && n <= s2end; m++, n++)
  70.                 l++;
  71.             if (l > 0)
  72.                 {
  73.                 if (l <= maxchars)
  74.                     j += l - 1;
  75.                 else
  76.                     {
  77.                     cl1 = i;
  78.                     cl2 = j;
  79.                     
  80.                     maxchars = l;
  81.                     l--;
  82.                     j += l;
  83.                     cr2 = j;
  84.                     cr1 = i+1;
  85.                     }
  86.                 }
  87.             }
  88.         }
  89.     *si = cl1;
  90.     *se = cr1;
  91.     *di = cl2;
  92.     *de = cr2;
  93.     return (maxchars);
  94.     }
  95.  
  96. pushst(si, se, di, de)
  97.     char *si, *se, *di, *de;
  98.     {
  99.     ststr1l[stcknum] = si;
  100.     ststr1r[stcknum] = se;
  101.     ststr2l[stcknum] = di;
  102.     ststr2r[stcknum] = de;
  103.     stcknum++;
  104.     }
  105.  
  106. popst(si, se, di, de)
  107.     char **si, **se, **di, **de;
  108.     {
  109.     stcknum--;
  110.     *si = ststr1l[stcknum];
  111.     *se = ststr1r[stcknum];
  112.     *di = ststr2l[stcknum];
  113.     *de = ststr2r[stcknum];
  114.     }